// https://soj.turingedu.cn/problem/60600/
// LCA（倍增版）
int n;
vector<int> adj[maxn];
int dep[maxn];
int f[maxn][21]; // f[i][j] = f[f[i][j - 1]][j - 1]

void init(int u, int p) {
    dep[u] = dep[p] + 1, f[u][0] = p;
    rf(j, 20) f[u][j] = f[f[u][j - 1]][j - 1];
    for (auto v : adj[u])
        if (v != p) init(v, u);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v); // keep deep[u] >= deep[v]
    for (int tmp = dep[u] - dep[v], j = 0; tmp > 0; ++j, tmp >>= 1) {
        if (tmp & 1) u = f[u][j]; // u move on
    }
    if (u == v) return u;
    for (int i = 20; i >= 0; --i) {
        if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}
